#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cstdlib>
#include<string>
#include <cstdlib>

using namespace std;
	
//para LIS1
vector<int> cost;  // vector de costos 
vector<int> parent; // vector de padres

// largest increasing subsequence O(n^2)
int LIS1(const vector<int>& input){
   cost  .assign(input.size(),  1);
   parent.assign(input.size(), -1);
   
   for(unsigned i = 0; i < input.size(); i++){
      for(unsigned j = i+1; j < input.size(); j++){
         if(input[j] > input[i] && (1 + cost[i]) > cost[j]){
            cost[j] = 1 + cost[i];
            parent[j] = i;
         }               
      }
   }
   
   int index = 0;
   
   for(unsigned i = 1; i < cost.size(); i++){
      if(cost[i] > cost[index]){
         index = i;
      }
   }
   
   return cost[index];
}

//imprimir la solucion de LIS1
void print_LIS1(int index, const vector<int>& input){
   cout << "solution size: " << cost[index] << endl;
   
   vector<int> v;

   v.push_back(input[index]);

   while(parent[index] != -1){
      v.push_back(input[parent[index]]);
      index = parent[index];
   }

   reverse(v.begin(), v.end());
   
   for(unsigned i = 0; i < v.size(); i++){
      cout << v[i] << endl;
   }
}

// Longest increasing subsequence O(nlogk) sin camino.
int LIS2(const vector<int>& input){
    set<int> s;
    set<int>::iterator k;

    for(unsigned i = 0; i < input.size(); i++){
        if(s.insert(input[i]).second){
           k = s.find(input[i]);
          
           if(++k != s.end()){
              s.erase(k);
           }
        }
    }
    return s.size();
}

// Longest increasing subsequence O(nlogk) con camino.
vector<int> LIS3(const vector<int> &input){
    vector<int> parent(input.size(),-1), res;
    map<int,int> m;
    map<int,int>::iterator k;

    for (unsigned i = 0; i < input.size();i++){  
        if (m.insert(make_pair(input[i], i)).second){  // si pudo insertar
           k = m.find(input[i]);
           
           if(k==m.begin()){
               parent[i]=-1;
           } else {
               parent[i]=(--k)->second;
               k++;
           }

           if(++k != m.end()){
              m.erase(k);
           }
         }
    }
    
    k = m.end();
    k--;
    int j = k->second;

    while (j != -1){
       res.push_back(input[j]);
       j = parent[j];
    }
    reverse (res.begin(),res.end());
    return res;
}

int main(){
   int a[] = {1,4,2,8,0,3,7,1};
   vector<int> in(a,a+8);
   
   cout << LIS1(in) << endl;
   cout << LIS2(in) << endl;
   cout << LIS3(in).size() << endl;      

   return 0;
}


